home *** CD-ROM | disk | FTP | other *** search
/ AI Game Programming Wisdom / AIGameProgrammingWisdom.iso / SourceCode / 02 Useful Techniques / 07 Vykruta / TransformMat.cpp < prev    next >
Encoding:
C/C++ Source or Header  |  2001-11-21  |  10.4 KB  |  264 lines
  1.        /////////////////////////////////////////////////////////
  2.       ////-------------------------------------------------////
  3.      ////          Fast Line-of-sight implementation      ////
  4.     //// (c) Copyright 2001, Tom Vykruta                 ////
  5.    ////              All Rights Reserved.               ////
  6.   ////    *not to be used without author's permission* ////
  7.  ////-------------------------------------------------////
  8. /////////////////////////////////////////////////////////
  9.  
  10.    //////////////////////////////////////////////////////
  11.   // TransformMat.cpp  : Generic code for Line-Of-Sight. Works in 3D.
  12.  //
  13. /////////////////////////////////////////////////////////
  14.  
  15. #include "stdafx.h"
  16. #include "LOSGridDemo.h"
  17. #include "TransformMat.h"
  18. #include "ChildView.h"
  19.  
  20. extern Layer g_Layer;
  21. extern CPaintDC* g_dc;
  22.  
  23. // This function would in reality do a more expensive ray-polygon test and return the impact point.
  24. // For purposes of this demo it only draws a ray representing the element division
  25. bool ElemDivisionCheck(const VECTOR3D& vFrom,const VECTOR3D& vTo, const int iElemX, const int iElemZ, VECTOR3D *pvImpact)
  26. {
  27.     VECTOR2D vTemp;
  28.     vTemp = VECTOR2D((float)iElemX * ELEMWID, (float)iElemZ * ELEMWID);
  29.     DrawLine2(vTemp, VECTOR2D(ELEMWID,ELEMWID), 2);
  30.  
  31.     return(FALSE);
  32. }
  33.  
  34. // This is the meat of the package, where it all happens
  35. // note: It is assumed that vFrom and vTo are already clipped to the layer's ABBox! 
  36. // squiggly lines ~^~^ represent visualization code
  37. bool Layer::DoesElemCollideRay(const VECTOR3D &vFrom, const VECTOR3D &vTo, VECTOR3D* pvImpact) const
  38. {
  39.     VECTOR2D _DEBUGvOrig(0,0);
  40.  
  41.     VECTOR2D vPathLu;
  42.     VECTOR2D vFromLu, vToLu;
  43.     int iNumSteps;
  44.     float rXCurr, rZCurr;
  45.  
  46.     vFromLu.Set(vFrom.x/rELEMWID,vFrom.z/rELEMWID); // convert to lu to make things easier
  47.     vToLu.Set(vTo.x/rELEMWID,vTo.z/rELEMWID);
  48.     {
  49.         VECTOR2D vLayerOrig;
  50.         vLayerOrig.Set( (float)GetXOrigin(), (float)GetZOrigin() );
  51.         vFromLu -= vLayerOrig;
  52.         vToLu -= vLayerOrig;
  53.     }
  54.  
  55.     vPathLu.Set(vToLu.x - vFromLu.x, vToLu.y - vFromLu.y);
  56.  
  57. // ~^~^~^~^~^~^~~^DEBUG CODE~^~^~^~^~^~^~~^~^~^~^~^~^~^~~^
  58. DrawLine2(VECTOR2D(vFromLu.x*ELEMWID, vFromLu.y*ELEMWID), VECTOR2D(vPathLu.x*ELEMWID, vPathLu.y*ELEMWID), 1);
  59. // ~^~^~^~^~^~^~~^~^~^~^~^~^~^~~^~^~^~^~^~^~^~~^
  60.  
  61.     // We will invert/mirror/rotate the grid in such a way that our line is always going +X, +Y, where slope is < 0.5.
  62.     TransformMatrix trans2dMat(vPathLu, vPathLu);
  63.     trans2dMat.TransformToGridSpace(vFromLu.x, vFromLu.y);
  64.     trans2dMat.TransformToGridSpace(vToLu.x, vToLu.y);
  65.     trans2dMat.TransformToGridSpace(vPathLu.x, vPathLu.y);
  66.  
  67. // ~^~^~^~^~^~^~~^DEBUG CODE~^~^~^~^~^~^~~^~^~^~^~^~^~^~~^
  68. VECTOR2D vTemp, vTempTo;
  69. DrawLine(VECTOR2D(vFromLu.x*ELEMWID, vFromLu.y*ELEMWID), VECTOR2D(vPathLu.x*ELEMWID, vPathLu.y*ELEMWID), 2);
  70. // ~^~^~^~^~^~^~~^~^~^~^~^~^~^~~^~^~^~^~^~^~^~~^
  71.  
  72.     // It' possible we will extend beyond layer boundaries.. make sure we dont try to check these
  73.     int iZAbsoluteStart = (int)floor(vFromLu.y);
  74.     int iZAbsoluteEnd   = (int)ceil(vToLu.y);
  75.  
  76.     const int iXMod = 0; // which way do we step to get a normal division line?
  77.     const int iZMod = 1;
  78.     const int iXModAlt = -1; // which way do we step to get alternate divison line?
  79.     const int iZModAlt = 0;
  80.  
  81.     int xShiftDivision, zShiftDivision;
  82.     int xShiftDivisionAlt, zShiftDivisionAlt;
  83.     xShiftDivision = 1; // offset vector from the origin of the element
  84.     zShiftDivision = 0;
  85.     xShiftDivisionAlt = 1;
  86.     zShiftDivisionAlt = 1;
  87.     trans2dMat.TransformOffsetToRealSpace(xShiftDivision,zShiftDivision);    
  88.     trans2dMat.TransformOffsetToRealSpace(xShiftDivisionAlt,zShiftDivisionAlt);    
  89.  
  90. // ~^~^~^~^~^~^~~^visualization code~^~^~^~^~~^~^~^~^~^~^~^~~^
  91. char message[128];
  92. g_dc->Rectangle(40,270,240,320);
  93. wsprintf(message, "NegX NegY FlipXY");
  94. g_dc->TextOut(50, 280, message, strlen(message) );
  95. wsprintf(message, "[ %i ][ %i ][ %i ]", (int)trans2dMat.matrix[TransformMatrix::tNegateX], 
  96.     (int)trans2dMat.matrix[TransformMatrix::tNegateY],
  97.     (int)trans2dMat.matrix[TransformMatrix::tInvertXY]);
  98. g_dc->TextOut(50, 300, message, strlen(message) );
  99.  
  100. g_dc->Rectangle(40,330,240,395);
  101. wsprintf(message, "Division Offsets (X,Y)");
  102. g_dc->TextOut(50, 340, message, strlen(message) );
  103. wsprintf(message, "Normal:    (%i, %i)", xShiftDivision, zShiftDivision );
  104. g_dc->TextOut(50, 360, message, strlen(message) );
  105. wsprintf(message, "Alternate: (%i, %i)", xShiftDivisionAlt, zShiftDivisionAlt );
  106. g_dc->TextOut(50, 375, message, strlen(message) );
  107. // ~^~^~^~^~^~^~~^~^~^~^~^~^~^~~^~^~^~^~^~^~^~~^
  108.  
  109.     // We have an entry point and exit point based on a layer's bounding box.
  110.     // figure out how much we need to extend the vFrom->vTo ray by to get to the first element cross.  We do this by snapping the vert along the XZ
  111.     // plane to the appropriate division line, then moving the other 2 components by same amount.
  112.  
  113.     float rStep, rStepY;
  114.     float rYCurrWu;
  115.     // Depending on which way we are stepping, pick the proper land division line to start on
  116.     // and fraction of total ray we have to move by to get to the preious and last element crossing
  117.     {
  118.         float rShiftFract, rShiftFractEnd;
  119.         float rXEnd, rZEnd;
  120.  
  121.         rXCurr = floor((double)vFromLu.x);
  122.         rXEnd = ceil((double)vToLu.x);
  123.         
  124.         rShiftFract = (vFromLu.x - rXCurr);
  125.         rShiftFract *= -1.0f / vPathLu.x;
  126.  
  127.         rShiftFractEnd = (vToLu.x - rXEnd);
  128.         rShiftFractEnd *= -1.0f / vPathLu.x;
  129.  
  130.         // Extend the ray - it's possible we will extend them off the layer, catch that later
  131.         rXCurr = vFromLu.x + vPathLu.x * rShiftFract;
  132.         rZCurr = vFromLu.y + vPathLu.y * rShiftFract;
  133.  
  134.         rXEnd = vToLu.x + vPathLu.x * rShiftFractEnd;
  135.         rZEnd = vToLu.y + vPathLu.y * rShiftFractEnd;
  136.  
  137.         rYCurrWu = vFrom.y + (vTo.y - vFrom.y) * rShiftFract;
  138.         vPathLu.Set( rXEnd - rXCurr, rZEnd - rZCurr );
  139.  
  140.         // figure out what our DX and DY is
  141.         float r1_Sections = 1.0f / vPathLu.dx;
  142.         rStep = vPathLu.dy * r1_Sections;
  143.  
  144.         // shift the Y component once again by the same fraction that x and z where moved by
  145.         rStepY = (vTo.y - vFrom.y) * (1.0f + -rShiftFract + rShiftFractEnd) * r1_Sections;
  146.  
  147.         // how many elements we iterate to reach the exit point
  148.         iNumSteps = (int)(vPathLu.dx + 0.5f) + 1; // 0.5f is for rounding (float) inaccuracies!
  149.     }
  150.  
  151.     // precompute 1/rstep for similar triangles when calculating height offset
  152.     const float r1_StepHeight = rStepY * (1.f / rStep);
  153.  
  154.     int iZTest, iXTest;
  155.     // to get around expensiv efloat->int conversions, using a float counter.. when it reaches 1, increment int
  156.     iZTest = (int)floor(rZCurr); // this cannot be FTOI because negative numbers woudln't be handled correctly
  157.     rZCurr = rZCurr - (float)iZTest;
  158.     iXTest = (int)(rXCurr + SIGN(rXCurr) * 0.5f); // 0.5f is for rounding (float) inaccuracies!
  159.  
  160. ///////////////////////////
  161.     enum eTestPoint    {etpBelow = 0, etpAbove, etpBetween, etpUninitialized};
  162.     eTestPoint ePosInitial = etpUninitialized; // our first test point lies abov eor below the layer..
  163.     eTestPoint ePosNow; // current testpoint
  164.     
  165.     BOOL fAltDivision = FALSE;
  166.  
  167.     int iXModReal, iZModReal, iXModAltReal, iZModAltReal;
  168.     // Figure out which way to step (in real grid space) to get the division line
  169.     iXModReal = iXMod; // in local grid space, we step +Z to get division
  170.     iZModReal = iZMod;
  171.     trans2dMat.TransformToRealSpace(iXModReal, iZModReal);
  172.     iXModAltReal = iXModAlt;// in local grid space, we step -X to get division
  173.     iZModAltReal = iZModAlt;
  174.     trans2dMat.TransformToRealSpace(iXModAltReal, iZModAltReal);
  175.  
  176.     int iXTestReal, iZTestReal;
  177.     float rHeight;
  178.     float rAltDivisionYCorrection = 0.0f;
  179.     for (int i = 0; i < iNumSteps; )
  180.     {
  181.         // Get XZ coordinates transformed into real grid space
  182.         iXTestReal = iXTest;
  183.         iZTestReal = iZTest;
  184.         trans2dMat.TransformToRealSpace(iXTestReal, iZTestReal);
  185.  
  186.         if (iZTest < iZAbsoluteStart || ((iZTest > iZAbsoluteEnd-1) && !fAltDivision) )
  187.             goto skip;
  188.  
  189.         rHeight = rYCurrWu;
  190.         
  191.         float rHeight1, rHeight2;
  192.         rHeight1 = VertHeight(iXTestReal, iZTestReal);
  193.         if (fAltDivision)
  194.             rHeight2 = VertHeight(iXTestReal + iXModAltReal, iZTestReal + iZModAltReal);
  195.         else
  196.             rHeight2 = VertHeight(iXTestReal + iXModReal, iZTestReal + iZModReal);
  197.  
  198.         ePosNow = (eTestPoint)(rHeight > rHeight1);
  199.  
  200.         if ( (eTestPoint)(rHeight > rHeight2) != ePosNow)
  201.             ePosNow = etpBetween;
  202.  
  203. // ~^~^~^~^~^~^~~^DEBUG CODE~^~^~^~^~^~^~~^~^~^~^~^~^~^~~^
  204.     vTemp.Set((float)iXTest*ELEMWID, (float)iZTest*ELEMWID);
  205.     vTempTo = VECTOR2D((fAltDivision ? iXModAlt : iXMod)*ELEMWID, (fAltDivision ? iZModAlt : iZMod)*ELEMWID);
  206.     DrawLine(vTemp, vTempTo);
  207.     
  208.     vTemp.Set(iXTestReal*ELEMWID, iZTestReal*ELEMWID);
  209.     vTempTo = VECTOR2D((fAltDivision ? iXModAltReal : iXModReal)*ELEMWID, (fAltDivision ? iZModAltReal : iZModReal)*ELEMWID);
  210.     DrawLine2(vTemp, vTempTo);
  211. // ~^~^~^~^~^~^~~^~^~^~^~^~^~^~~^~^~^~^~^~^~^~~^
  212.  
  213.         if (ePosInitial == etpUninitialized)
  214.             ePosInitial = ePosNow; // first time, initialize height, don't check verts
  215.         else
  216.         {
  217.             // when i is 0, just initialize the etpPosNow
  218.             if (ePosNow == etpBetween || ePosInitial  != ePosNow)
  219.             {
  220.                 ePosInitial = ePosNow;
  221.                  const int& xShift = (fAltDivision == FALSE) ? xShiftDivision : xShiftDivisionAlt;
  222.                 const int& zShift = (fAltDivision == FALSE) ? zShiftDivision : zShiftDivisionAlt;
  223.                 // In transformed space, to get the corner of elem, step back by 1X.  Transform this to get the real step.
  224.                 VECTOR3D vFromLocal = vFrom;
  225.                 vFromLocal -= this->GetOrigin();
  226.                 VECTOR3D vToLocal = vTo;
  227.                 vToLocal -= this->GetOrigin();
  228.                 if ( ElemDivisionCheck(vFromLocal,vToLocal,iXTestReal - xShift, iZTestReal - zShift, pvImpact) )
  229.                 {
  230.                     if (pvImpact)
  231.                         *pvImpact += this->GetOrigin();
  232.                       return(TRUE);
  233.                 }
  234.             }
  235.         }
  236.  
  237. skip:
  238.         if (fAltDivision)// Go through the same loop, but with this flag set as false
  239.         {
  240.             fAltDivision = FALSE;
  241.             rYCurrWu += rAltDivisionYCorrection;
  242.         }
  243.         else
  244.         {
  245.             // move along our ray, to the next element division.
  246.             rYCurrWu += rStepY;
  247.             iXTest += 1;
  248.             rZCurr += rStep;
  249.             if ( rZCurr > 1.0f)
  250.             {
  251.                 fAltDivision = TRUE; // we crossed a division that doesnt lie along the common axis..
  252.                 rZCurr -= 1.0f;
  253.                 iZTest += 1;
  254.                 // Since we are checking the alt division, but our height check is a measure at the regular division, we must figure out the
  255.                 // old height using similar triangles.  equation: (1.0 * rZCurr) / rStep;  gives us the horizontal fraction to step back by.
  256.                 rAltDivisionYCorrection = r1_StepHeight * rZCurr;
  257.                 rYCurrWu -= rAltDivisionYCorrection;
  258.             }
  259.             i++;
  260.         }
  261.     }
  262.     return(FALSE);
  263. }
  264.